//https://leetcode.cn/problems/3sum/

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int r = nums.size() - 1;
        int n = r;
        vector<vector<int>> ret;
        for (int i = 0; i < n;) {
            if (nums[i] > 0)
                break;
            int l = i + 1;
            r = n;
            while (l < r) {
                int temp = nums[l] + nums[r];
                int A = -nums[i];
                if (temp < A) {
                    l++;
                    continue;
                }
                else if (temp > A) {
                    r--;
                    continue;
                }
                else {
                    ret.push_back({ nums[l], nums[r], nums[i] });

                    while (l < r && nums[l + 1] == nums[l])
                        l++;
                    while (l < r && nums[r - 1] == nums[r])
                        r--;
                    l++;
                    r--;
                    continue;
                }
            }
            while (i < n && nums[i] == nums[i + 1])
                i++;
            i++;

        }
        return ret;
    }
};

//-4 -1 -1 0 1 2